package org.lep.leetcode.datastructure.tree.lowestcommonancestor;

import com.sun.xml.internal.org.jvnet.mimepull.CleanUpExecutorFactory;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
import org.lep.leetcode.trappingrainwater.TrappingRainWater;
import org.omg.PortableInterceptor.INACTIVE;

/**
 * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
 *
 * @author lverpeng
 * @since 2020/3/11
 */
public class LowestCommonAncestorOfBinaryTree {
    /**
     * 深度优先遍历树，使用栈来辅助回溯
     * 先找到其中一个节点p或者q，并且保存该节点的所有父节点加入父节点集合
     * 再查找另外一个节点，然后依次查找父节点是否在上面的父节点集合中
     * 第一个出现在集合中的即为要找的公共祖先
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stack = new Stack<>();
        Map<TreeNode, TreeNode> parent = new HashMap<>();
        stack.push(root);
        parent.put(root, null);
        while (!parent.containsKey(p) || !parent.containsKey(q)) {
            root = stack.pop();
            if (root.left != null) {
                parent.put(root.left, root);
                stack.push(root.left);
            }
            if (root.right != null) {
                parent.put(root.right, root);
                stack.push(root.right);
            }
        }
        Set<TreeNode> pAncestor = new HashSet<>();
        while (p != null) {
            pAncestor.add(p);
            p = parent.get(p);
        }

        while (!pAncestor.contains(q)) {
            q = parent.get(q);
        }
        return q;
    }

    private TreeNode ancestor = null;
    public boolean recurseTree(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return false;
        }
        // 剪枝
        if (this.ancestor != null) {
            return false;
        }
        int left = recurseTree(root.left, p, q) ? 1 : 0;
        int right = recurseTree(root.right, p, q) ? 1 : 0;
        int mid = (root == p || root == q) ? 1 : 0;
        if (left + right + mid >= 2) {
            this.ancestor = root;
            return true;
        }
        return left + right + mid > 0;
    }

    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        recurseTree(root, p, q);
        return this.ancestor;
    }
}